Multiple Recursive Calls: Fibonacci Sequence, Part 1¶
Introducing multiple recursive calls¶
Along with factorials and the Towers of Hanoi, the Fibonacci sequence is one of the classic introductions to recursion. I’ve chosen to include it at a significantly later point in this guide, since Fibonacci has deep implications for understanding recursion, and particularly the efficiency of certain recursive algorithms. It shows that the most intuitive recursive solution may not be desirable, and will force us to look for better ways of implementing this technique.
Let’s first look at the sequence itself, which is seeded with 0 and 1. Each succeeding Fibonacci number is the sum of the two previous ones. Written in the form of a list, the first ten Fibonacci numbers are:
n 0 1 2 3 4 5 6 7 8 9
fib(n) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
When we ask for fib(n) we are asking for the place that nth number occupies in the Fibonacci sequence, similar to if we asked for the 10th prime number, or the 6th triangular number. If we were to represent this recursively, a few things immediately stand out.
The first is that, like pascal(), we are generating the sequence by looking backwards to retrieve earlier terms that we need to perform the computation. In fact, we need to go all the way back to the base case to be able to calculate the intermediate values.
Secondly, both 0 and 1 are the seeds needed to kick off the sequence What does this imply for a recursive solution? We’ve seen something similar with our function to determine palindromicity: for pal(), we had to account for the fact that any string either has an even or an odd number of characters, which meant we needed two base cases. Likewise, fib() has to account for 0 and 1:
fib(n):
if n == 0 or n == 1:
return n
else:
# some code
We return n here because if we want fib(0), we can’t very well return 1, can we? (We can also write if n < 2: return n, which is a bit more compact.) It’s true that, as we decrement fib(n), we will always return 1, but we’ll also hit fib(0) far more often than you think, as we’ll see.
When considering the recursive case, let’s go back to the way the sequence is generated. In terms of any number n > 2, another way to say “add the previous two numbers” is “add n - 1 with n - 2”. In terms of generalizing this to the function, we can write:
fib(n) == fib(n - 1) + fib(n - 2)
In other words, we need to consult the sequence twice in order to get to n. This seems fairly straightforward if we are calculating fib(2): we just add up both base cases and return the result, which is 1.
n 0 1 0 1 2
fib(n) [0, 1] —> [0, 1, 1]
Adding the next term in a sequence is always easy if you have the formula and all the preceding values. But what if we wanted to know fib(3)?
n 0 1 0 1 2 3
fib(n) [0, 1] —> [0, 1, ?, fib(3)]
Working from our ‘(n - 1) + (n - 2)’ formula, to get fib(3) we first need to get fib(2) so we can add it to fib(1), which we already know is 1. And to get fib(2) we’ll need to invoke fib(1) and fib(0), which we know are 1 and 0. This need to work backwards to the base case and then move forwards again suggests that the Fibonacci sequence lends itself to recursion. In fact, there’s not much more to the code than what we’ve just reasoned through:
fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 1) + fib(n - 2)
Recursively speaking, we go back to the base case in order to get the value we are sure of, then add up all the returned values on the trip back through the call stack. Since all of the computation happens at the moment of the recursive calls, it’s appropriate to put fib(n - 1) + fib(n - 2) in the return statement. It’s just a matter of backfilling the sequence until we have all of the terms needed to derive the desired nth number.
At first glance this solution looks entirely reasonable. But a closer look at the return statement reveals quite a devil in the details. Let’s map out what this might look like for fib(3) using our usual ‘talking algorithm’ approach:
- Global frame: Hey
fib(), computefib(3)for me. - Frame 1 of
fib(): I don’t know whatfib(3)is because first I need to computefib(2)and add it tofib(1)(return fib(2) + fib(1)). Sincefib(2)is first, let me evaluate it: - Frame 2 of
fib(): I don’t know whatfib(2)is because I first need to computefib(1)and add it tofib(0):return fib(1) + fib(0). Sincefib(1)comes first, let me evaluate it: - Frame 3 of
fib(): I know thatfib(1) == 1, since it’s a base case, so I’ll return the result as1. Closing frame 3. - Frame 2 of
fib(): Thanks. I now have:return 1 + fib(0), so let’s evaluatefib(0): - Frame 4 of
fib(): I know thatfib(0) == 0, since it’s a base case, so I’ll return the result as0. Closing frame 4. - Frame 2 of
fib(): I can now completereturn 1 + 0so I’m returning1to frame 1. Closing frame 2. - Frame 1 of
fib(): Ok, I now knowfib(2) == 1so I can update my return statement toreturn 1 + fib(1), but I still can’t return the answer since I now need to evaluatefib(1) - Frame 5 of
fib(): I know thatfib(1) == 1is a base case so I will return1. Frame 5 now closed. - Frame 1 of
fib(): Ok, I now knowfib(1) == 1so I can finish evaluating the return statement and close frame 1:return 1 + 1 - Global frame: I’ve received
2fromfib()
That turns out to be a lot of steps to compute the next term in the sequence. Here’s an illustration of the calls as they unfold, frame by frame.
.jpg)
Figure 1. The Fibonacci call stack for fib(3)
So far we’ve been illustrating the call stack from the bottom up. Just as cafeteria trays are stacked on top of one another and removed in a last-in-first-out (LIFO) order, that’s the way recursion creates and destroys frames. But multiple recursive calls introduce a branching structure that is conceptually closer to a tree. I find top-down diagrams much easier to read, because we’ve been taught to be top-down readers. So it’s much more intuitive to follow the branches until we ‘get to the bottom’ of a chain of logic. In this case, branches are successive recursive calls, and every time the base case is achieved (and the recursive cascade reversed), we record it as a leaf.
An important part of reading these diagrams is the order in which computation happens. You can follow this by the frame numbering, keeping in mind that a computation completed at the base case will be returned to the calling frame, but that that frame may well initiate another branch of frame(s) in order to address the second recursive call in the return statement. So the program flow for the sequence of frames for fib(3) would be:
global-1-2-3-2-4-2-1-5-1-global
If this diagram of fib(3) seems a bit more complex than expected, things get noticeably worse for the next value of n. If we were to ask for the fourth Fibonacci number, our diagram would look like this:
.jpg)
Figure 2. The Fibonacci call stack for fib(4)
You can see that all the computations that make up fib(3) are a subset of fib(4), and that all of fib(2) is a subset of fib(3), but also that fib(2) shows up a second time in the right portion of fib(4)’s tree! From a more general perspective, you can now see the return statement embodies two separate sides of the tree, where the computation of the first (left) term must be completed before computation of the second (right) term can be undertaken:
return fib(3) + fib(2)
^^^^^^ ^^^^^^
left right
The diagram for fib(4) points out two important consequences of multiple recursive calls. We’re already familiar with the first one: once a function begins recursing, it continues until the base case. But in the case of multiple recursive calls, getting to the base case means splitting off and leaving the second (right) call for later. Of course, since the function calls itself, this means there is a split for every call. Likewise, what gets addressed first every time is the left term, so the recursion works its way through every left term until the base case is reached. Multiple recursion implies that we traverse the entire height of the tree before computing any other branches. In keeping with the top-down visualization, this is known as ‘depth-first search’.
In addition to depth-first search, the tree is gradually traversed left-to-right, which you can follow by the 1-2-3-2-4-2-1-5-1 sequence described above.
It’s worth pointing out that, at the moment we return to frame 1, we have recursed our way through the left-hand side of the tree. We now have the answer to the first term of fib(n - 1) + fib(n - 2). If the tree were symmetrical, we would say that we were at its midpoint. We repeat the process for the right side, continuing to move depth-first and gradually left-to-right. The last base case we hit is the leaf at the rightmost position of the diagram.
We’ll use this attribute of recursion to our advantage in the algorithms following this section.
Of course, there are several ways to think about this: you could think of it as a metaphoric tree, in which case branches spring from a trunk and each branch ends in leaves. Here you might think of it as a ‘height-first’ search. There are also diagrams that grow the recursive calls horizontally, such that the ‘tree’ is on its side, branching horizontally from left to right. However, most texts use the top-to-bottom, left-to-right metaphor.
Measuring efficiency and complexity¶
The second consequence of multiple recursion is even more important, at least for our need to compute larger Fibonacci numbers. It may not have been apparent from fib(3), but fib(4) shows that there is some amount of redundant computation going on, and if there’s one thing that programmers despise it’s redundant computation.
Here, in the first, left-handed branch of fib(4) we compute fib(2) as part of fib(3). As we return the results to frame 1, we also find ourselves having to compute fib(2) from scratch for the second, right-handed recursive call, fib(n - 2). The fact that fib(2) is a subtree of both fib(3) and fib(4) isn’t doing us any favors. You could say it’s a classic case of the right hand not knowing what the left hand is doing.
The problem is only compounded when we get into double-digit Fibonacci numbers. This becomes computationally very expensive. In fact, try calculating fib(45) and see if you can’t make and eat a sandwich while you wait. If we include a step counter that simply ticks off the number of times fib() calls itself, we see a real explosion:
n fib(n) calls
0 0 1
1 1 1
2 1 3
3 2 5
4 3 9
5 5 15
6 8 25
7 13 41
8 21 67
9 34 109
10 55 177
11 89 287
12 144 465
13 233 753
14 377 1,219
15 610 1,973
… … …
35 9,227,465 29,860,703
While dramatic, tabulating the number of calls doesn’t give us much of an indication of how long this might take. Fortunately, we can further analyize our algorithms by measuring code execution speed. A good tool for this is Python’s timeit module, which is designed for testing small pieces of code. To do so, first write this at the top of your code:
import timeit
Then wrap up your function call like so:
print(timeit.timeit('fib(35)', globals=globals(), number=1))
The keyword argument number sets the number of times timeit() runs the function. Since we’re only interested in a rough cut, you can simply set it to 1.
Note
If you’re running Python from the command line or a similar REPL session, include globals=globals() as another kwarg, so that timeit() can find the global frame. Otherwise Python will throw an error.
Our complete code for measuring fib() looks like this:
import timeit
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 1) + fib(n - 2)
print(timeit.timeit('fib(35)', globals=globals(), number=1), 'seconds')
>>> 2.999023314 seconds
However, given hardware differences, my execution time will likely be different from yours. Computer science has therefore come up with a formal way of studying computational complexity, independent of hardware and such variables. I’m not going to dwell on complexity in this guide, but you can see that fib() is quite an expensive way of going about things. The complexity of what people have come to call the ‘naive Fibonacci algorithm’ isn’t quite 2**n, where n is the Fibonacci number we’re after - 2**n would be the complexity of a perfect binary tree, where both the left and right sides have an equal number of nodes and leaves. But it’s not far off either. Since the left-hand side of the tree generated by fib(n - 1) will always be larger than the right-hand side, fib(n - 2), we say that the fib(n) tree is asymmetrical. In the end, the efficiency is closer to 1.6**n, which is still exponential and therefore to be avoided.
It looks like recursion has finally failed us. Sure, the code is very pretty to look at, but useless if it doesn’t give the answer. On the other hand, if we could find a way to 1) store the result of each computation once we made it, and 2) refer back to that result when needed, we could potentially cut down on the number of steps. And we can, using a technique known as ‘memoization’, which I’ll cover in the next section.
Heuristics and Exercises¶
♦ Recursion may be powerful, elegant and compact, but can also yield certain solutions that are computationally unwieldy, if not inachievable. Solutions that imply returning multiple recursive calls should be approached with extreme caution.
♦ Multiple recursive calls expand call diagrams as linear ‘stacks’ to branching ‘trees’. When following the flow of a multiply recursing function, keep in mind that the function will recurse fully to the base case of its first recursive call before evaluating any other calls.
♦ This depth-first search is complemented by the fact that the tree will fill itself out by moving in a gradual, left-to-right direction. The final base case to be evaluated will be the rightmost leaf in the diagram.
Exercise: The tribonacci series is a generalization of the Fibonacci sequence where each term is the sum of the three preceding terms.
The first few terms of the sequence are:
[0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]
The tribonacci sequence is defined as follows:
fn(0) == fn(1) == 1
fn(2) == 2
fn(n) == fn(n - 1) + fn(n - 2) + fn(n - 3)
Create a recursive function trib() that returns the tribonacci number for any given n. How would you write the base case? At what point does the sequence noticeably slow down?
Take a few minutes to draw out, by hand, the call diagram for trib(5). What does the branching look like? How would you characterize the computational complexity of a function like trib() versus that of fib()?
Now measure performance by modifying both fib() and trib() to use timeit(). Write a loop that will record the times for a range of values for both functions. Do the results match up with your intuition? Why or why not?